1981C - Turtle and an Incomplete Sequence - CodeForces Solution

def path(x, y):
    ma = max(x, y)
    mi = min(x, y)

    u = [ma]
    v = [mi]

    while u[-1] != v[-1]:
        if ma > mi:
            ma //= 2
            u.append(ma)
        else:
            mi //= 2
            v.append(mi)

    return v + u[::-1][1:]

def solve():
    n = int(input())
    a = [int(i) for i in input().split()]
    d = []

    for i in range(n):
        if a[i] != -1:
            d.append(i)

    if not d:
        for i in range(0, n, 2):
            a[i] = 1
            if i + 1 != n:
                a[i + 1] = 2
        return a
        
    for i in range(d[0] - 1, -1, -1):
        if a[i + 1] == 1:
            a[i] = a[i + 1] * 2
        else:
            a[i] = a[i + 1] // 2

    for i in range(d[-1] + 1, len(a)):
        if a[i - 1] == 1:
            a[i] = a[i - 1] * 2
        else:
            a[i] = a[i - 1] // 2

    for i in range(0, len(d) - 1):
        p = path(a[d[i]], a[d[i + 1]])

        if d[i + 1] - d[i] + 1 < len(p):
            return [-1]

        if (d[i + 1] - d[i] + 1 - len(p)) % 2:
            return [-1]

        if p[0] != a[d[i]]:
            p.reverse()

        p = p[1:-1]

        for j in range(d[i] + 1, d[i + 1]):
            if j - d[i] - 1 >= len(p):
                if j == 1:
                    if a[j - 1] == 1:
                        a[j] = a[j - 1] * 2
                    else:
                        a[j] = a[j - 1] // 2
                else:
                    a[j] = a[j - 2]
            else:
                a[j] = p[j - d[i] - 1]

    return a

for _ in range(int(input())):
    print(*solve())